package Test.offer;


/**
 * @ClassName P35
 * @Description
 * @Company inspur
 * @Author Kevin
 * @Date 2020/8/1 18:55
 * @Version 1.0
 */
public class P35 {

    /**
     * @ClassName Problem35
     * @Description 复制复杂链表
     * @Company inspur
     * @Author Kevin
     * @Date 2020/5/23 10:42
     * @Version 1.0
     */
    public class Problem35 {
        /*
         * 主程序（包含三步）
         */
        public ComplexListNode cloneList(ComplexListNode head) {
            cloneNodes(head);           //1.复制结点
            connectSiblingNodes(head);  //2.设置sibling
            return reconnectNodes(head);//3.拆分长链表
        }

        /*
         * 第一步：复制每个结点，并插入到原始节点的后面
         */
        private void cloneNodes(ComplexListNode head) {
            ComplexListNode pNode = head;
            while (pNode != null) {
                ComplexListNode cloneNode = new ComplexListNode(pNode.val);
                cloneNode.next = pNode.next;
                pNode.next = cloneNode;
                pNode = cloneNode.next;
            }
        }

        /*
         * 第二步：根据原结点的sibling，设置复制结点的sibling
         */
        private void connectSiblingNodes(ComplexListNode head) {
            ComplexListNode pNode = head;
            while (pNode != null) {
                if (pNode.sibling != null) {//必须考虑到siblingNode==null的情况！
                    pNode.next.sibling=pNode.sibling.next;
                }
                pNode = pNode.next.next;
            }
        }

        /*
         * 第三步：将长链表拆分成原始链表和复制链表（根据奇偶位置）
         */
        private ComplexListNode reconnectNodes(ComplexListNode head) {
            ComplexListNode clonedHead=null;
            ComplexListNode clonedNode=null;
            ComplexListNode pNode=head;
            if(head!=null) {
               clonedHead = head.next;
               clonedNode = pNode.next;
               pNode.next = clonedNode.next;
               pNode = pNode.next;
            }
            while(pNode!=null) {
                clonedNode.next = pNode.next;
                clonedNode = clonedNode.next;
                pNode.next = clonedNode.next;
                pNode = pNode.next;
            }
            return clonedHead;
        }
    }

    class ComplexListNode {
        int val;
        ComplexListNode next = null;
        ComplexListNode sibling = null;

        ComplexListNode (int label) {
            this.val = label;
        }
    }
}
